package 剑指offer;

import org.junit.Test;

public class _51数组中的逆序对 {
	@Test
	public void test() {
		int[] nums = { 7, 5, 6, 4 };
		
		System.out.println(reversePairs(nums));
	}

	/**
	 * 
	 * @time 2021年3月20日下午3:05:32
	 * 
	 * @param nums
	 * @return int
	 *
	 * @see归并排序 思想解答
	 */
	public int reversePairs(int[] nums) {
		if (nums.length < 2) {
			return 0;
		}
		int []temp = new int[nums.length]; 
		return mergeSort(nums, 0, nums.length-1,temp);

	}
	/**
	 * 
	 *@time 2021年3月20日下午8:06:48
	 * 
	 *@param nums
	 *@param left
	 *@param right
	 *@return int
	 *
	 *@see
	 *当 i = m + 1 时： 代表左子数组已合并完，
	 *因此添加右子数组当前元素 tmp[j]，并执行 j = j + 1
	 *否则，当 j = r + 1 时： 代表右子数组已合并完，因此添加左子数组当前元素 tmp[i] ，并执行 i = i + 1 ；
	 *否则，当 tmp[i]≤tmp[j] 时： 添加左子数组当前元素 tmp[i] ，并执行 i=i+1；
	 *否则（即tmp[i]>tmp[j]）时： 添加右子数组当前元素tmp[j] ，并执行 j = j + 1；
	 *此时构成 m - i + 1个「逆序对」，统计添加至 res ；
	 */
	public int mergeSort(int[] nums, int left, int right,int [] temp) {
		if (left >= right)
			return 0;
		int mid = (left + right) / 2;
		int res = mergeSort(nums, left, mid,temp) + mergeSort(nums, mid + 1, right,temp);

		int i = left, j = mid + 1;
	
		for (int k = left; k <= right; k++) {
			temp[k] = nums[k];
		}
		for (int k = left; k <= right; k++) {
			if (i == mid+1) {
				nums[k] = temp[j++];
			}else if (j == right+1||temp[i] <= temp[j]) {
				nums[k] = temp[i++];
			}else {
				nums[k] = temp[j++];
				res += mid-i+1;
			}
		}
		return res;

	}

	public void swap(int[] nums, int a, int b) {
		int temp = nums[a];
		nums[a] = nums[b];
		nums[b] = temp;
	}

}
